#include<iostream>
#include<vector>
#include<stack>

using namespace std;

struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} 
};

class Solution {
public:
    vector<int> inorderTraversal(TreeNode* root) {
        vector<int> result;  // 定义存储中序遍历结果的数组
        stack<TreeNode*> stk;  // 定义辅助栈
        TreeNode* node = root;  // 指针 root 所指向的地址复制给指针 node

        while (node || !stk.empty()) {  // 循环条件
            while (node) {  // 将当前节点以及其左子树全部压入栈中
                stk.push(node);
                node = node->left;
            }
            node = stk.top();  // 取出栈顶元素
            stk.pop(); // 从栈 stk 中弹出栈顶元素
            result.push_back(node->val);  // 将栈顶元素的值添加到结果数组中
            node = node->right;  // 转向右子树
        }

        return result;  // 返回结果数组
    }
};

int main() {
    // 构造二叉树
    TreeNode* root = new TreeNode(1);
    root->right = new TreeNode(2);
    root->right->left = new TreeNode(3);

    // 中序遍历
    Solution s;
    vector<int> result = s.inorderTraversal(root);

    // 输出结果
    cout << "[";
    for (int i = 0; i < result.size(); i++) {
        if (i > 0) cout << ",";
        cout << result[i];
    }
    cout << "]" << endl;

    return 0;
}